package Review.MapAndSet;

import java.util.HashMap;
import java.util.HashSet;

// key-value 模型
public class HashBuck {
   static class Node {
      public int key;
      public int val;
      public Node next;
      Node random;

      public Node(int key, int val) {
         //this.key = key;
         this.val = val;
         this.random = null;
      }
   }

   public Node[] array = new Node[10];
   public int usedSize;
   public static final double LOAD_FACTOR = 0.75f;

   public void put(int key, int val) {
      int index = key % array.length;
      Node cur = array[index];
      Node node = new Node(key, val);
      while (cur != null) {
         if (cur.key == key) {
            cur.val = val;
         }
         cur = cur.next;
      }
      //走到这里说明没有找到当前链表中有key这个节点
      node.next = array[index];
      array[index] = node;
      usedSize++;
      //走到这里说明数组容量不够要扩容
      if (loadfactor()>=LOAD_FACTOR){
         resize();
      }
   }

   private void resize() {
      Node[] num = new Node[2*array.length];
      for (int i=0;i<array.length;i++){
         Node cur = array[i];
         while (cur !=null){
            int index = cur.key%num.length;
            Node prev = cur.next;
            cur.next = num[index];
            num[index] = cur;
            cur = prev;
         }
      }
   }
   private double loadfactor(){
      return  usedSize*1.0/array.length;
   }
   public int getVal(int key){
      int index = key%array.length;
      Node cur = array[index];
      while (cur !=null){
         if (cur.key==key){
            return cur.val;
         }
         cur = cur.next;
      }
      return 0;
   }
   class Node1 {
      int val;
      Node1 next;
      Node1 random;

      public Node1(int val) {
         this.val = val;
         this.next = null;
         this.random = null;
      }
   }
   public Node1 copyRandomList(Node1 head) {
      HashMap<Node1,Node1>map = new HashMap<>();
      Node1 cur = head;
      while (cur !=null){
         Node1 node = new Node1(cur.val);
         map.put(cur,node);
         cur = cur.next;
      }
      cur = head;
      while (cur !=null){
         map.get(cur).next = map.get(cur.next);
         map.get(cur).random = map.get(cur.random);
         cur =cur.next;
      }
      return map.get(head);
   }
   //宝石余石头
   public int numJewelsInStones(String jewels, String stones) {
      HashSet <Character> set = new HashSet<>();
      for (int i=0;i<jewels.length();i++){
         char ch = jewels.charAt(i);
         set.add(ch);
      }
      int count =0;
      for (int i = 0; i < stones.length(); i++) {
         char ch = stones.charAt(i);
         if (set.contains(ch)) {

            count++;
         }
      }
      return count;
   }
   //坏键盘打字
   public  static  void brokenKeyboard(String str1,String str2){
      str1 = str1.toUpperCase();
      str2 = str2.toUpperCase();
      HashSet<Character> setGood = new HashSet<>();
      for (int i = 0; i < str2.length(); i++) {
         char ch = str2.charAt(i);
         setGood.add(ch);
      }
      HashSet<Character> setBroken = new HashSet<>();
      for (int i = 0; i < str1.length(); i++) {
         char ch = str1.charAt(i);
         if (!setGood.contains(ch)&&!setBroken.contains(ch)){
            setBroken.add(ch);
            System.out.print(ch);
         }
      }
   }
   }
